/*
 * @lc app=leetcode.cn id=69 lang=cpp
 *
 * [69] Sqrt(x)
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int mySqrt(int x) {
        int max = 46340;
        int min = 0;
        int result = (max+min)/2;
        while(!(result*result<=x 
        and (result+1)*(result+1)>x)){
            if (max-min==1){
                if ((min*min<=x)and(max*max)>x){
                    return min;
                }else{return max;}
            }

            if (result*result>x){
                max = result-1;
                result = (max+min)/2;
            }else{
                min = result;
                result = (max+min)/2;
            }
            // printf("check %d %d %d\n", max, min, result);
        }
        return result;
    }
};
// int main(){
//     Solution mySolution;
//     mySolution.mySqrt(9);
// }
// @lc code=end

